package 笔试.度小满1;

import 算法.NiuKe.ListNode;

import java.io.FileReader;
import java.util.*;

/**
 * @author:谢君臣
 * @Date:2021/10/23-16:42
 * @version:1.0
 * @function:
 */
public class Main1 {
    public static void main(String[] args) {
        ArrayList<String> abc = getPermutation("ABC");
        System.out.println(abc.toString());
    }
    public static ArrayList<String> getPermutation(String A) {
        // write code here
        char[]arr = A.toCharArray();
        Arrays.sort(arr);
        StringBuilder r = new StringBuilder();
        for (int i = arr.length-1; i >=0 ; i--) {
                r.append(arr[i]);
        }
        wall(new StringBuilder(),new HashSet<>(),r.toString());
        return res;
    }
    static ArrayList<String> res = new ArrayList<>();
    private static void wall(StringBuilder stringBuilder, HashSet<Object> objects, String a) {
        if (objects.size()==a.length()){
            if (stringBuilder.length()<=11&&stringBuilder.toString().equals(stringBuilder.toString().toUpperCase()))
                res.add(stringBuilder.toString());
            return;
        }
        Set<Character> un = new HashSet<>();
        for (int i = 0; i < a.length(); i++) {
            char c = a.charAt(i);
            if (un.contains(c)||objects.contains(i))
                continue;
            un.add(c);
            objects.add(i);
            stringBuilder.append(c);
            wall(stringBuilder, objects, a);
            objects.remove(i);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }

    public void reorderList(ListNode head) {
        Deque<ListNode> deque = new LinkedList<>();
        ListNode temp = head;
        temp = temp.next;
        while (temp!=null){
            deque.offer(temp);
            temp = temp.next;
        }
        boolean f = true;
        while (!deque.isEmpty()){
            if (f){
                ListNode c = deque.pollLast();
                c.next = null;
                head.next = c;
                f = false;
            }else {
                ListNode c = deque.pollFirst();
                c.next=null;
                head.next=c;
                f = true;
            }
            head= head.next;
        }
    }
    public int numDistinct (String S, String T) {
        // write code here
        int[][] dp = new int[T.length()+1][S.length()+1];
        for (int i = 0; i < S.length()+1; i++)dp[0][i] =1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (T.charAt(i-1)==S.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1]+ dp[i][j-1];
                }else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[T.length()][S.length()];
    }
}
